// Definition for a Node.

//N叉树结构
class Node {
public:
    int val;
    vector<Node*> children; //因为是N叉树，孩子节点较多

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

//广度优先搜索 BFS
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        //判断树是否为空
        if(!root)
        {
            return {};
        }

        vector<vector<int>> ans;

        queue<Node*> q;//留意是指针队列，不是示例队列
        q.push(root); //加载第一层节点

        while(!q.empty())
        {
            int cnt=q.size();
            vector<int> level;

            for(int i=0;i<cnt;i++)
            {
                Node* cur=q.front();
                q.pop();
                //保存数值
                level.push_back(cur->val);
                //将下一层节点按顺序加载到队列中
                for(Node* child: cur->children)
                {
                    q.push(child);
                }
            }
            //每层遍历完之后，将level保存在vector<vector<int>>
            ans.push_back(move(level));
        }
        return ans;
    }
};